\section{Related Work}
\label{sec:related}

\subsection{Temporal planning}

Temporal planners can be divided into two types according to the degree of concurrency. 
The first type is temporally simple planners
that cannot handle concurrency. Most existing temporal planners
are temporally simple~\cite{Mausam06,Cushing07}, such
as~ZENO~\cite{Penber94}, TMP~\cite{Smith99},
TLPlan~\cite{Bacchus01}, TP4~\cite{Haslum01}, LPG~\cite{Gerevi02},
LPGP~\cite{Long03}, TALPlan~\cite{Kvarnstrom03},
VHPOP~\cite{Younes03}, SAPA~\cite{Do03}, SGPlan~\cite{Wah06}, CPT~\cite{Vidal06} and LPG-td~\cite{Gerevini08}.
Temporal simple planners cannot find a plan for this temporal expressive problem, since no sequential plan exists.
%SAPA also cannot solve it since it does not allow any action between the start and end point of durative actions.
%Part of the reason is that these existing planners make some
%assumptions on how actions interact with one another. 
The second type is temporally expressive planners that can handle concurrency.
Existing PDDL based temporally expressive planners that we are aware
of are TM-LPSAT~\cite{Shin:aaai04}, Crikey2~\cite{Coles08},
Crikey3~\cite{Coles08:AIJ}, LPG-c~\cite{Gerevini10} and TFD~\cite{Eyerich09}. 
TM-LPSAT compiles temporal metric problems with continuous time 
into linear programming with SAT (LP-SAT) constraints and
uses a LP-SAT solver~\cite{Wolfman99} to find a solution. 
Crikey2 and Crikey3 combine planning and scheduling for temporal problems.
They perform a state-based heuristic search, which uses enforced
hill climbing (EHC) followed by best-first search if EHC fails. 
LPG-c~\cite{Gerevini10} introduces a revised representation, temporal action graph (TA-graph) with concurrency, that supports action concurrency. 
TFD~\cite{Eyerich09} adds time increments of $\epsilon > 0$ after each action insertion to support this concurrency.
A recent work in~\cite{Hu07} theoretically studies compilation of temporally expressive problems
into a constraint satisfaction formulation.
All these temporally expressive planners cannot optimize action costs. 

%However, as we have discussed early, metric 
%temporal planners need to handle objective functions
%that are based on both makespan and action costs.


%The lack of optimal temporally
%expressive planners is in sharp contrast with the reality that many
%real-world planning problems are highly concurrent.
%To the contrary, currently many real-world problems are still simply modeled as propositional planning. 
%Part of the reason, might be due to that it is usually much more complex than propositional planning~\cite{Rintanen07:AAAI}.

\subsection{Cost sensitive planners}

Recent temporal planners that aim at optimizing makespan and action costs
include MO-GRT~\cite{Refanidis01} and
SAPA~\cite{Do03}. MO-GRT extends the heuristic state-space search to temporal planning. 
SAPA is a domain-independent heuristic forward
chaining planner that can handle durative actions, metric resource
constraints, and deadline goals. It is designed to deal with 
multi-objective metrics, such as makespan and action costs.
Nevertheless, neither MO-GRT nor SAPA can handle temporally
expressive domains.

For classical STRIPS planning without durative actions and concurrency, there exist planners that can optimize action costs. 
Most planners minimizing total action costs use heuristic state space search, such as LAMA~\cite{Richter08,Richter10}, HSP$^*_0$,
HSP$^*_F$~\cite{Haslum08}, FF($h_a$)~\cite{keyder08},
CO-PLAN~\cite{Robinson08-coplan}. 
Research has been carried out on optimizing the {\em number of
actions}~\cite{vidal:IPC-04,haslum:ICAPS-00,buttner:ICAPS-05,helmert:AAAI08},
which is a special case of optimizing the total action costs.
SAT-based classical STRIPS planners have also been extended to
optimize action costs. Three recent representative works,
Plan-A~\cite{IPC08a}, SATPlan$^{\prec}$~\cite{Giu07} and
PWM-RSAT~\cite{Robinson10}, can find plans that minimize total
action costs but are unable to handle temporal features. Plan-A completely
searches the space of the SAT instance translated from a deterministic
planning problem to minimize its total costs. SATPlan$^{\prec}$ makes
improvements in finding solutions with better total action costs by
using OPTSAT~\cite{Giu:JELIA-06}, a tool for solving SAT constrained
optimization problems. PWM-RSAT modifies the SAT solver RSAT2.02 to
create an effective partial weighted Max-SAT procedure for problems
where all soft constraints are unit clauses. 
%These planners
%Nevertheless, none of them is capable of handling temporally
%expressive domains.

\subsection{SAT solvers}
Translating metric planning problems into SAT formulations and
calling MinCost SAT or Max-SAT solvers to solve them form another
choice for optimizing action costs~\cite{Robinson10}. 
There are also several MinCost SAT solvers, such as Scherzo~\cite{Coudert96},
Bsolo~\cite{Manquinho02}, Eclipse~\cite{Li04}, and
MinCostChaff~\cite{Fu06}. MinCostChaff is the first MinCost SAT solver that 
incorporates many modern SAT techniques~\cite{Fu06,Moskewica01}. 
Experimental results show that MinCostChaff has orders of magnitude 
of performance improvement over
other MinCost SAT solvers. 
However, comparing to Max-SAT solvers,
MinCostChaff is slower since its
lower bounding function does not perform well especially on large
problems~\cite{Fu06}. 
%Thus, we use Max-SAT solvers and our new BB-DPLL solvers to solve the MinCost SAT
%formulations instead of using the MinCostChaff solver.
%Recently, there has been an increasing interest in the development of Max-SAT solvers. 

Max-SAT solvers have also been extensively studied.
There are at least three different types of Max-SAT solvers, including extended DPLL algorithms based on branch-and-bound
procedure: BF~\cite{Borchers97}, AMP~\cite{Alsinet03},
SZ~\cite{Shen02}, MaxSolver~\cite{Xing05maxsolver} and
MINIMAXSAT~\cite{Heras07minimaxsat,Heras07minimaxsat-b}; an OR-based
Pseudo Boolean algorithm: PBS~\cite{Dixon02}; and a weighted CSP-based
algorithm: WCSP~\cite{Givry03}. 
%Since 2006, a Max-SAT competition takes place every year. 
Besides SAT4J~\cite{sat4j}, the winner of
weighted partial Max-SAT (industrial track) in the Max-SAT 2009
Competition, there are some other efficient solvers, such as
IncWMaxSatz~\cite{Darras07}, W-MaxSatz~\cite{Li06,Li07,Li09}, and
Clone~\cite{Pipatsrisawat07clone}. 

